|
課程名稱 |
演算法
Algorithms |
|
開課學期 |
107-2 |
|
授課對象 |
電機工程學系 |
|
授課教師 |
江蕙如 |
|
課號 |
EE4033 |
|
課程識別碼 |
901 39000 |
|
班次 |
01 |
|
學分 |
3.0 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期五2,3,4(9:10~12:10) |
|
上課地點 |
博理112 |
|
備註 |
總人數上限：80人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1072EE4033_01 |
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
The study of algorithms is at the heart of computer science. This course focuses on fundamental results in this area, including the unifying principles and underlying concepts of algorithm design and analysis.
We expect everyone to be comfortable reading, even writing, proofs. Several programming assignments will be given to embody the ideas. Moreover, we hope that everyone can learn general problem-solving techniques.
Intended audience:
1. who are interested in computer science
2. who are computing something
3. who are learning problem-solving techniques |
|
課程目標 |
1. Study unifying principles and concepts of algorithm design
2. Polish your critical thinking and problem-solving technique |
|
課程要求 |
Prerequisite: two out of the following four courses
1. Data structures
2. Discrete mathematics
3. Computer programming in C
4. Computer programming in C++ |
|
預期每週課後學習時數 |
|
|
Office Hours |
每週四 13:00~15:00
每週五 13:30~14:00 備註： Made by appointment.
TA: Thursdays;
Instructor: Fridays
|
|
指定閱讀 |
J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006 (Cornell) |
|
參考書目 |
1. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-
Hill,
2007 (UC Berkeley)
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to
Algorithms, 3rd Ed., McGraw Hill/MIT Press, 2009 (Bible! MIT)
3. Princeton slides: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/
Recommended books on graph theory:
1. Douglas B. West, Introduction to Graph Theory, 2nd Edition, Pearson, 2000.
2. 演算法觀點的圖論 (Graph Theory, with an Algorithmic Perspective)作者：張鎮華 |
|
評量方式
(僅供參考) |
|
No. |
項目 |
百分比 |
說明 |
|
1. |
Adjustment |
0% |
Adjustment: +-5% for each item |
2. |
In-class tests |
50% |
Midterm: 25% + Final: 25% |
3. |
Programming projects |
40% |
Two mini-projects: 20% + term project: 20% |
4. |
Homework assignments |
10% |
|
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
02/22 |
Overview and introduction |
|
第2週 |
02/23 |
Basics of algorithm analysis |
|
第3週 |
03/08 |
Graphs |
|
第4週 |
03/15 |
Graphs |
|
第5週 |
03/22 |
Greedy algorithms |
|
第6週 |
03/29 |
Greedy algorithms |
|
第7週 |
04/05 |
Tomb Sweeping Day (no classes) |
|
第8週 |
04/12 |
Divide and conquer |
|
第9週 |
04/19 |
Divide and conquer + master theorem |
|
第10週 |
04/26 |
Midterm |
|
第11週 |
05/03 |
Dynamic programming |
|
第12週 |
05/10 |
Dynamic programming |
|
第13週 |
05/17 |
Network flow |
|
第14週 |
05/24 |
NP completeness |
|
第15週 |
05/31 |
Amortized analysis |
|
第16週 |
06/07 |
Dragon Boat Festival (Holiday) |
|
第17週 |
06/14 |
Final |
|
第18週 |
06/21 |
Project presentation |
|
第19週 |
06/28 |
Linear programming (Appendix) |
|